package tulingxueyuan117;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 13:03
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class p29_二叉树最大深度_104 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(9);
        TreeNode node3 = new TreeNode(20);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        int res = maxDepth(node1);
        System.out.println(res);
    }
//    递归
//    public static int maxDepth(TreeNode root) {
//        if(root==null) return 0;
//        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
//    }
//    循环迭代
    public static int maxDepth(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
//            size用来记录本层级的节点是否已经处理完
            int size = queue.size();
            while (size > 0){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }
}
